/**
 * 求数组中逆序对的总数
 * example:[7,5,6,4]
 * return: 5
 * 解法：归并排序
 * @param {number[]} nums 
 */
var reversePairs = function (nums) {
    const len = nums.length
    // arr作为归并排序的结果数组
    let arr = Array(len)

    // l和r表示区间左右端点
    function getCount(l, r) {
        // 结束条件
        if (l >= r) {
            return 0
        }
        const mid = (l + r) >> 1
        let res = 0
        res += getCount(l, mid)
        res += getCount(mid + 1, r)
        // 归并排序
        let k = l
        let i = l, j = mid + 1
        while (i <= mid || j <= r) {
            if (j > r || (i <= mid && nums[i] <= nums[j])) {
                arr[k++] = nums[i++]
            } else {
                // 出现逆序对
                arr[k++] = nums[j++]
                // res加上 左侧数组 中剩余的元素数量
                res += mid - i + 1
            }
        }
        // 更新排好序的数组
        for (let i = l; i <= r; i++) {
            nums[i] = arr[i]
        }
        return res
    }

    return getCount(0, len - 1)
}